import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 二分法插入 {
    
    public static void main(String[] args) {
        
        Integer[] arr = new Integer[]{4,5,7,10,29};
        int temp = 11;

        System.out.println(Arrays.toString(arr));

        List<Integer> result = insertValue(new ArrayList<Integer>(Arrays.asList(arr)), temp);

        result.stream().map(s -> s+", ").forEach(System.out::print);
        System.out.println();
    }

    private static List<Integer> insertValue(ArrayList<Integer> list, int temp){

        int left =0;
        int right = list.size() - 1;
        int middle = -1;

        while (right >= left) {
            
            middle = (left+right) / 2;

            if(list.get(middle) > temp){

                right = middle - 1;
            } else {

                left = middle + 1;
            }
        }

        list.add(middle, temp);


        return list;

    }
}
